package leetcode_900;

/**
 *@author 周杨
 *MaximizeDistanceToClosestPerson_849 给定一个数组表示座位  1是有人坐 0是无人坐 问坐在哪个座位 可以使左右有人的座位最远
 *describe:用左右数组标记 取极大极小值 AC 28%
 *2018年11月3日 上午11:48:06
 */
public class MaximizeDistanceToClosestPerson_849 {
	public int maxDistToClosest(int[] seats) {
        int left[]=new int[seats.length];
        int right[]=new int[seats.length];
        left[0]=seats[0]==1?0:Integer.MAX_VALUE;//0表示不能坐  用Integer.MAX_VALUE表示无人
        for(int i=1;i<seats.length;++i) {
        	if(seats[i]==1)
        		left[i]=0;
        	else {
        		if(left[i-1]==Integer.MAX_VALUE)
        			left[i]=left[i-1];
        		else
        			left[i]=left[i-1]+1;
        	}
        }
        right[seats.length-1]=seats[seats.length-1]==1?0:Integer.MAX_VALUE;
        for(int i=seats.length-2;i>=0;--i) {
        	if(seats[i]==1)
        		right[i]=0;
        	else {
        		if(right[i+1]==Integer.MAX_VALUE)
        			right[i]=right[i+1];
        		else
        			right[i]=right[i+1]+1;
        	}
        }
        int max=0;
        for(int i=0;i<left.length;++i) {
        	if(left[i]==0)
        		continue;
        	max=Math.max(max, Math.min(left[i], right[i]));
        }
        return max;
    }
}
